from typing import List


def combine(states: List, T: int) -> List:
    '''
    输入 所有状态的集合 序列长度
    返回 所有可能出现的状态序列
    '''
    res = []

    def backtrace(cur_seq: List):
        # 已经取够了
        if len(cur_seq) >= T:
            res.append(cur_seq)
            return

        # 序列的下一个状态选择
        for s in states:
            backtrace(cur_seq + [s])
    
    backtrace([])
    return res

def format(seq: List) -> List:
    '''
    0 -> w1
    1 -> w2
    i -> wi+1
    ...
    '''
    res = []
    for i in seq:
        res.append('w' + str(i+1))
    return res
# for debug
# W = ["w1", "w2", "w3"]

# S = combine(W,4)

# for i,s in enumerate(S):
#     print(i+1,s)

        



